/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 如果 cur 不空 ：入栈然后向左走
// 如果 cur 空 ：出栈然后回溯 cur 为出栈的元素，然后向右走
 
 // step 1# 定义栈结构体
 typedef struct {
     struct TreeNode** data;   // 存储 TreeNode* 的数组
     int top;                  // 栈顶指针
     int capacity;             // 栈容量
 } Stack;
 
 // step 2# 创建栈
 Stack* createStack(int capacity) {
     Stack* stack = (Stack*)malloc(sizeof(Stack));                            // 分配栈结构
     stack->data = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * capacity);  // 分配节点指针数组
     stack->top = -1;
     stack->capacity = capacity;
     return stack;
 }
 
 // step 3# 栈是否为空
 bool isEmpty(Stack* stack) {
     return stack->top == -1;
 }
 
 // step 4# 压栈操作
 void push(Stack* stack, struct TreeNode* node) {
     if (stack->top + 1 < stack->capacity) {
         stack->data[++(stack->top)] = node;
     }
 }
 
 // step 5# 弹栈操作
 struct TreeNode* pop(Stack* stack) {
     if (!isEmpty(stack)) {
         return stack->data[(stack->top)--];
     }
     return NULL;
 }
 
 // step 6# 查看栈顶元素
 struct TreeNode* peek(Stack* stack) {
     if (!isEmpty(stack)) {
         return stack->data[stack->top];
     }
     return NULL;
 }
 
 // step 7# 释放栈内存
 void freeStack(Stack* stack) {
     free(stack->data);
     free(stack);
 }
 
 // step 8# 中序遍历主函数：左 -> 中 -> 右（非递归）
 int* inorderTraversal(struct TreeNode* root, int* returnSize){
     int* result = (int*)malloc(sizeof(int) * 100);     // 假设最大节点数为100
     *returnSize = 0;
 
     Stack* stack = createStack(100);                   // 创建辅助栈
     struct TreeNode* cur = root;                       // 当前指针
 
     // step 8.1# 遍历整个树
     while (cur != NULL || !isEmpty(stack)) {
         if (cur != NULL) {
             // step 8.2# 不断访问左节点，并压入栈
             push(stack, cur);                          // 当前节点入栈
             cur = cur->left;                           // 向左走
         } else {
             // step 8.3# 左边到底后，从栈中弹出处理节点
             cur = pop(stack);                          // 取出栈顶节点
             result[(*returnSize)++] = cur->val;        // 中：访问该节点
             cur = cur->right;                          // 右：转向右子树
         }
     }
 
     freeStack(stack);                                  // 释放栈内存
     return result;
 }
 